package binarytree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author: 海琳琦
 * @Date: 2021/9/9 21:11
 */
public class Title100 {
    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(){}
        TreeNode(int val, TreeNode left, TreeNode right){
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public static void main(String[] args) {

    }

    /**
     * 广度优先遍历
     * @param p
     * @param q
     * @return
     */
    private static boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q==null){
            return true;
        }
        if(p==null||q==null){
            return false;
        }
        Queue<TreeNode> queue1 = new LinkedList<>();
        Queue<TreeNode> queue2 = new LinkedList<>();
        queue1.offer(p);
        queue2.offer(q);
        //若节点都为空跳出则两树相等
        while(!queue1.isEmpty()&&!queue2.isEmpty()){
            //一次只对比一个（与层次遍历一次读取一层整个节点稍有不同）
            TreeNode pol = queue1.poll();
            TreeNode pol2 = queue2.poll();
            if(pol.val!=pol2.val){
                return false;
            }
            //异或运算符^
            if(pol.left==null ^ pol2.left==null){
                return false;
            }
            if(pol.right==null ^ pol2.right==null){
                return false;
            }
            if(pol.left!=null){
                queue1.offer(pol.left);
            }
            if(pol.right!=null){
                queue1.offer(pol.right);
            }
            if(pol2.left!=null){
                queue2.offer(pol2.left);
            }
            if(pol2.right!=null){
                queue2.offer(pol2.right);
            }
        }
        return queue1.isEmpty()&&queue2.isEmpty();
    }


    /**
     * 先序判断
     */
//    private static boolean isSameTree(TreeNode p, TreeNode q) {
//        if(p==null&&q==null){
//            return true;
//        }
//        if(p==null||q==null){
//            return true;
//        }
//        if(p.val==q.val){
//            return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
//        }else{
//            return false;
//        }
//    }
}
